home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-19 / iritsm3s.zip / SCANDATA.C < prev    next >
C/C++ Source or Header  |  1991-09-08  |  17KB  |  515 lines
  1. /*****************************************************************************
  2. *   Routines to    scan convert the input (polygons), which is sorted into         *
  3. * global hash table PolyHashTable according to polygons Ymin.             *
  4. *                                         *
  5. * Written by:  Gershon Elber                Ver 2.0, Mar. 1990   *
  6. *****************************************************************************/
  7.  
  8. #ifdef __MSDOS__
  9. #include <stdlib.h>
  10. #endif /* __MSDOS__ */
  11.  
  12. #include <math.h>
  13. #include <time.h>
  14. #include <stdio.h>
  15. #include <string.h>
  16. #include "program.h"
  17. #include "iritprsr.h"
  18.  
  19. /* #define DEBUG            /* Add some printing to stderr routines. */
  20.  
  21. #define Z_BUFFER_MIN_Z    -32767
  22.  
  23. static GifPixelType *MaskSubScanLine = NULL;
  24. static GifPixelType *ImageScanLine = NULL;
  25. static GifPixelType *MaskScanLine = NULL;
  26. static int *ZBuffer;
  27.  
  28. static void InitScanLine(void);
  29. static void ScanOnePolygon(IPPolygonStruct *PPolygon, int Level);
  30. static IPVertexStruct *GetNeighborVrtx(IPPolygonStruct *PPolygon,
  31.                        IPVertexStruct *V, IPVertexStruct *NotV);
  32. static void UpdateScanLine(int x1, int z1, int x2, int z2,
  33.                         int Color1, int Color2);
  34.  
  35. #ifdef DEBUG
  36. void PrintHashTable(void);
  37. void PrintPolygon(IPPolygonStruct *PPolygon);
  38. void PrintImageScanLine(void);
  39. #endif /* DEBUG */
  40.  
  41. /*****************************************************************************
  42. * Routine to scan convert all polygons in PolyHashTable.             *
  43. * The real images goes to GifFile, while GifMask (if not NULL) will have a   *
  44. * booleam mask, where image was created.                     *
  45. *****************************************************************************/
  46. void ScanConvertData(GifFileType *GifFile, GifFileType *GifMask)
  47. {
  48.     char *ImageSubBGScanLine;
  49.     int i, j, k, OrigScrnXSize, OrigScrnYSize, *ImageSubScanLine,
  50.     SubSamplePixelSquare, *MinIntensityIndex, SubSamplePixel,
  51.     MinYScan = 0, SubSampleLine = 0, LineCount = 0;
  52.     long SaveTime = time(NULL);
  53.     IPPolygonStruct *PPolygon, *PPolygonLast;
  54.     GifPixelType *OneSubScanLine;
  55.  
  56.     OrigScrnXSize = GlblShadeInfo.ScrnXSize;
  57.     OrigScrnYSize = GlblShadeInfo.ScrnYSize;
  58.  
  59.     GlblShadeInfo.ScrnXSize *= GlblShadeInfo.SubSamplePixel;
  60.     GlblShadeInfo.ScrnYSize *= GlblShadeInfo.SubSamplePixel;
  61.  
  62.     if (GlblShadeInfo.SubSamplePixel > 1) {
  63.     OneSubScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
  64.                         OrigScrnXSize);
  65.     ImageSubScanLine = (int *) MyMalloc(sizeof(int) *
  66.                         OrigScrnXSize);
  67.     ImageSubBGScanLine = (char *) MyMalloc(sizeof(char) *
  68.                         OrigScrnXSize);
  69.     }
  70.     ImageScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
  71.                         GlblShadeInfo.ScrnXSize);
  72.     if (GifMask != NULL) {
  73.     if (GlblShadeInfo.SubSamplePixel > 1)
  74.         MaskSubScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
  75.                         OrigScrnXSize);
  76.     MaskScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
  77.                         GlblShadeInfo.ScrnXSize);
  78.     }
  79.     ZBuffer = (int *) MyMalloc(sizeof(int) * GlblShadeInfo.ScrnXSize);
  80.  
  81.     MinIntensityIndex = GlblShadeInfo.MinIntensityIndex;
  82.     SubSamplePixel = GlblShadeInfo.SubSamplePixel;
  83.     SubSamplePixelSquare = SQR(SubSamplePixel);
  84.  
  85.     fprintf(stderr, "\nPass 4, Level [%4d] =      ",
  86.         OrigScrnYSize);
  87.  
  88.     for (i = 0; i < GlblShadeInfo.ScrnYSize; i++) {         /* Scan line i: */
  89.     /* First lets scan and delete all polygons below this scan line: */
  90.     for (j = MinYScan; j <= i; j++) {
  91.         PPolygon = PPolygonLast = PolyHashTable[j];
  92.         while (PPolygon) {
  93.         if (PPolygon -> Ymax < i) {         /* Delete this polygon. */
  94.             /* If it is first one, update the hash table also. Note  */
  95.             /* we dont free the polygon as, we are not going to      */
  96.             /* allocate anything any more, so why bather.         */
  97.             if (PPolygon == PolyHashTable[j])
  98.             PolyHashTable[j] = PPolygonLast = PPolygon =
  99.                 PPolygon -> Pnext;
  100.             else
  101.             PPolygonLast -> Pnext = PPolygon = PPolygon -> Pnext;
  102.         }
  103.         else {
  104.             PPolygonLast = PPolygon;
  105.             PPolygon = PPolygon -> Pnext;
  106.         }
  107.         }
  108.         /* If this level is empty - advance the minimum level to scan: */
  109.         if (j == MinYScan && PolyHashTable[j] == NULL) MinYScan++;
  110.     }
  111.  
  112.     /* New do the scan conversion of the active polygons: */
  113.     InitScanLine();
  114.     for (j = MinYScan; j <= i; j++) {
  115.         PPolygon = PPolygonLast = PolyHashTable[j];
  116.         while (PPolygon) {
  117.         ScanOnePolygon(PPolygon, i);
  118.         PPolygonLast = PPolygon;
  119.         PPolygon = PPolygon -> Pnext;
  120.         }
  121.     }
  122.  
  123.     if (SubSamplePixel > 1) {
  124.         if (SubSampleLine == 0) {      /* Reset the sub sumpling buffers. */
  125.         memset(ImageSubScanLine, 0,
  126.             sizeof(int) * OrigScrnXSize);
  127.         memset(OneSubScanLine, 0,
  128.             sizeof(GifPixelType) * OrigScrnXSize);
  129.         memset(ImageSubBGScanLine, 0,
  130.                    sizeof(char) * OrigScrnXSize);
  131.         if (GifMask) memset(MaskSubScanLine, 0,
  132.                   sizeof(GifPixelType) * OrigScrnXSize);
  133.         }
  134.         for (j = 0; j < GlblShadeInfo.ScrnXSize; j++)
  135.         if (ImageScanLine[j] == 0)
  136.             ImageSubBGScanLine[j / SubSamplePixel]++;
  137.         else {
  138.             k = j / SubSamplePixel;
  139.             ImageSubScanLine[k] += ImageScanLine[j];
  140.             OneSubScanLine[k] = ImageScanLine[j];
  141.             if (GifMask) MaskSubScanLine[k] = MaskScanLine[j] != 0 ||
  142.                                MaskSubScanLine[k];
  143.         }
  144.         SubSampleLine++;
  145.         if (SubSampleLine == SubSamplePixel) {
  146.         for (j = 0; j < OrigScrnXSize; j++) {
  147.             /* Instead of Back Ground - add the lowest intensity of */
  148.             /* This color. Note we still may have problems if two   */
  149.             /* colors are averaged to a color index in between...   */
  150.             if (ImageSubScanLine[j] > 0)
  151.             ImageSubScanLine[j] += ImageSubBGScanLine[j] *
  152.                     MinIntensityIndex[OneSubScanLine[j]];
  153.             OneSubScanLine[j] = ImageSubScanLine[j] /
  154.                             SubSamplePixelSquare;
  155.         }
  156.         fprintf(stderr, "\b\b\b\b\b%5d", ++LineCount);
  157.  
  158. #            ifndef DEBUG_NO_GIF
  159.             EGifPutLine(GifFile, OneSubScanLine,
  160.                 OrigScrnXSize);
  161.             if (GifMask)
  162.             EGifPutLine(GifMask, MaskSubScanLine,
  163.                     OrigScrnXSize);
  164. #            endif /* DEBUG_NO_GIF */
  165.  
  166.         SubSampleLine = 0;
  167.         }
  168.     }
  169.     else {
  170.         fprintf(stderr, "\b\b\b\b\b%5d", ++LineCount);
  171.  
  172. #        ifndef DEBUG_NO_GIF
  173.         EGifPutLine(GifFile, ImageScanLine, GlblShadeInfo.ScrnXSize);
  174.         if (GifMask)
  175.             EGifPutLine(GifMask, MaskScanLine,
  176.                 GlblShadeInfo.ScrnXSize);
  177. #        endif /* DEBUG_NO_GIF */
  178.     }
  179.     }
  180.  
  181.     fprintf(stderr, ",  %ld seconds.", time(NULL) - SaveTime);
  182.  
  183.     GlblShadeInfo.ScrnXSize = OrigScrnXSize;
  184.     GlblShadeInfo.ScrnYSize = OrigScrnYSize;
  185. }
  186.  
  187. /*****************************************************************************
  188. * Reset all buffers to clear state:                         *
  189. *****************************************************************************/
  190. static void InitScanLine(void)
  191. {
  192.     memset(ImageScanLine, 0, sizeof(GifPixelType) * GlblShadeInfo.ScrnXSize);
  193.  
  194.     if (MaskScanLine)
  195.         memset(MaskScanLine, 0, sizeof(GifPixelType) * GlblShadeInfo.ScrnXSize);
  196.  
  197.     /* Set all Zbuffer to Z_BUFFER_MIN_Z. Can be done in a regular loop as:  */
  198.     /* for (i = 0; i < ScrnXSize; i++) ZBuffer[i] = Z_BUFFER_MIN_Z;         */
  199.     /* As memset allows setting of only one byte, the minimum we can set     */
  200.     /* here is -32640 which is 0x8080, so we do that instead:             */
  201.     memset(ZBuffer, 0x80, sizeof(int) * GlblShadeInfo.ScrnXSize);
  202. }
  203.  
  204. /*****************************************************************************
  205. * Scan convert one polygon:                             *
  206. * 1. If one of the left/right boundaries is found to be below current level  *
  207. *    that boundary edge is updated.                         *
  208. * 2. Interpolate the Color and Z value of the intersection of scan line with *
  209. *    the boundaries and call UpdateScanLine to update the buffers.         *
  210. *****************************************************************************/
  211. static void ScanOnePolygon(IPPolygonStruct *PPolygon, int Level)
  212. {
  213.     int x1, z1, x2, z2, Color1, Color2;
  214.     RealType t1, t2, *Coord1, *Coord2;
  215.     IPVertexStruct *V;
  216.     PolygonScanConvertStruct
  217.     *PScan = (PolygonScanConvertStruct *) PPolygon -> PAux;
  218.  
  219.     /* Stage 1 - verify that both boundaries are in range: */
  220.     if (PScan -> Bndry1.MaxEdgeY < Level) {
  221.     V = PScan -> Bndry1.VMinY;
  222.     PScan -> Bndry1.VMinY = PScan -> Bndry1.VMaxY;
  223.     PScan -> Bndry1.VMaxY =
  224.         GetNeighborVrtx(PPolygon, PScan -> Bndry1.VMaxY, V);
  225.     PScan -> Bndry1.MaxEdgeY =
  226.         (int) PScan -> Bndry1.VMaxY -> Coord[1];
  227.     }
  228.  
  229.     if (PScan -> Bndry2.MaxEdgeY < Level) {
  230.     V = PScan -> Bndry2.VMinY;
  231.     PScan -> Bndry2.VMinY = PScan -> Bndry2.VMaxY;
  232.     PScan -> Bndry2.VMaxY =
  233.         GetNeighborVrtx(PPolygon, PScan -> Bndry2.VMaxY, V);
  234.     PScan -> Bndry2.MaxEdgeY =
  235.         (int) PScan -> Bndry2.VMaxY -> Coord[1];
  236.     }
  237.  
  238.     /* Stage 2 - evaluate the interpolated X & Z for this line and call      */
  239.     /* UpdateScanLine with them. Note we could do it using some sort of DDA  */
  240.     /* (integer arithmetic) but as UpdateScanLine is much more expensive     */
  241.     /* we will gain almost nothing in speed, doing that.             */
  242.     /* Also as this polygon assumed to intersect with the scan line using    */
  243.     /* integer arithmetic, it might not be so, when we actuallt evaluate it. */
  244.     /* We simply quit if that is the case.                     */
  245.     Coord1 = PScan -> Bndry1.VMinY -> Coord;
  246.     Coord2 = PScan -> Bndry1.VMaxY -> Coord;
  247.     if (ABS(Coord2[1] - Coord1[1]) == 0.0)
  248.     t1 = 0.5;
  249.     else
  250.     t1 = (Coord2[1] - Level) / (Coord2[1] - Coord1[1]);
  251.     if (t1 < 0.0 || t1 > 1.0) return;
  252.  
  253.     x1 = Coord1[0] * t1 + Coord2[0] * (1.0 - t1);
  254.     z1 = Coord1[2] * t1 + Coord2[2] * (1.0 - t1);
  255.  
  256.     Coord1 = PScan -> Bndry2.VMinY -> Coord;
  257.     Coord2 = PScan -> Bndry2.VMaxY -> Coord;
  258.     if (ABS(Coord2[1] - Coord1[1]) == 0.0)
  259.     t2 = 0.5;
  260.     else
  261.     t2 = (Coord2[1] - Level) / (Coord2[1] - Coord1[1]);
  262.     if (t2 < 0.0 || t2 > 1.0) return;
  263.  
  264.     x2 = Coord1[0] * t2 + Coord2[0] * (1.0 - t2);
  265.     z2 = Coord1[2] * t2 + Coord2[2] * (1.0 - t2);
  266.  
  267.     if (GlblShadeInfo.Gouraud) {
  268.     /* Need to interpolate the colors as well: */
  269.     Color1 = (int) (PScan -> Bndry1.VMinY -> Color * t1 +
  270.             PScan -> Bndry1.VMaxY -> Color * (1.0 - t1));
  271.     Color2 = (int) (PScan -> Bndry2.VMinY -> Color * t2 +
  272.             PScan -> Bndry2.VMaxY -> Color * (1.0 - t2));
  273.     UpdateScanLine(x1, z1, x2, z2, Color1, Color2);
  274.     }
  275.     else {
  276.     /* Flat shading - all vertices has same intensity - pick one: */
  277.     UpdateScanLine(x1, z1, x2, z2, PScan -> Bndry1.VMinY -> Color,
  278.                        PScan -> Bndry1.VMinY -> Color);
  279.     }
  280. }
  281.  
  282. /*****************************************************************************
  283. * Returns the other neighbor of vertex V in polygon PPolygon which is not    *
  284. * the neighbor NotV.                                 *
  285. *****************************************************************************/
  286. static IPVertexStruct *GetNeighborVrtx(IPPolygonStruct *PPolygon,
  287.                        IPVertexStruct *V, IPVertexStruct *NotV)
  288. {
  289.     int i;
  290.     IPVertexStruct *List2,
  291.     *List = PPolygon -> PVertex;
  292.  
  293.     /* Find index of vertex V. */
  294.     for (i = 0; List != V; i++, List = List -> Pnext);
  295.  
  296.     if (i == 0) {
  297.     /* The vertex is first - its neighbors are second and last in list.  */
  298.     if (PPolygon -> PVertex -> Pnext == NotV) {
  299.         /* We need the last one: */
  300.         for (List2 = PPolygon -> PVertex;
  301.          List2 -> Pnext != NULL;
  302.          List2 = List2 -> Pnext);
  303.         return List2;
  304.     }
  305.     else
  306.         return PPolygon -> PVertex -> Pnext;
  307.     }
  308.     else if (List -> Pnext == NULL) {
  309.     /* The vertex is last - its neighbors are first and second from last.*/
  310.     if (PPolygon -> PVertex == NotV) {
  311.         /* We need the second from last: */
  312.         for (List2 = PPolygon -> PVertex;
  313.          List2 -> Pnext != List;
  314.          List2 = List2 -> Pnext);
  315.         return List2;
  316.     }
  317.     else
  318.         return PPolygon -> PVertex;
  319.     }
  320.     else {
  321.     if (List -> Pnext == NotV) {
  322.         for (List2 = PPolygon -> PVertex;
  323.          List2 -> Pnext != List;
  324.          List2 = List2 -> Pnext);
  325.         return List2;
  326.     }
  327.     else
  328.         return List -> Pnext;
  329.     }
  330. }
  331.  
  332. /*****************************************************************************
  333. * Update the scan line itself by linearly interplate the two end points for  *
  334. * all internal points of scan line if closer than old data.             *
  335. *****************************************************************************/
  336. static void UpdateScanLine(int x1, int z1, int x2, int z2,
  337.                         int Color1, int Color2)
  338. {
  339.     int i, Dx, Dz, Dc, Az, Ac, x, z, Color;
  340.     RealType t;
  341.  
  342.     if (x2 < x1) {
  343.     i = x2; x2 = x1; x1 = i;
  344.     i = z2; z2 = z1; z1 = i;
  345.     i = Color2; Color2 = Color1; Color1 = i;
  346.     }
  347.     if (x1 < 0) {
  348.     /* Update lower limit to zero: */
  349.     if (x2 == x1) return;
  350.     t = -x1 / (x2 - x1);
  351.     x1 = 0;
  352.     z1 = (int) (z1 * (1.0 - t) + z2 * t);
  353.     Color1 = (int) (Color1 * (1.0 - t) + Color2 * t);
  354.     }
  355.     if (x2 >= GlblShadeInfo.ScrnXSize) {
  356.     /* Update upper limit to GlblShadeInfo.ScrnXSize - 1: */
  357.     if (x2 == x1) return;
  358.     t = (x2 - (GlblShadeInfo.ScrnXSize - 1)) / (x2 - x1);
  359.     x2 = GlblShadeInfo.ScrnXSize - 1;
  360.     z2 = (int) (z1 * t + z2 * (1.0 - t));
  361.     Color2 = (int) (Color1 * t + Color2 * (1.0 - t));
  362.     }
  363.  
  364.     Dx = x2 - x1;
  365.     x = x1;
  366.     Dz = z2 - z1;
  367.     Az = -Dx;                  /* DDA accumulator of Z interpolation. */
  368.     z = z1;
  369.     Color = Color1;
  370.     if (GlblShadeInfo.Gouraud) {
  371.     Dc = Color2 - Color1;         /* Needed if Gouraud shading is in use. */
  372.     Ac = -Dx;          /* DDA accumulator of Color interpolation. */
  373.     }
  374.  
  375.     /* We are going to execute the loop once but might be stack forever in   */
  376.     /* one of the internal interplation loops, so make it non zero:         */
  377.     if (Dx == 0) Dx = 999;
  378.  
  379.     if (Dz > 0) {
  380.     while (x <= x2) {
  381.         /* Update buffers iff is closer to view point: */
  382.         if (ZBuffer[x] < z) {
  383.         ZBuffer[x] = z;
  384.         ImageScanLine[x] = Color;
  385.         if (MaskScanLine != NULL) MaskScanLine[x] = 1;
  386.         }
  387.         else if (ZBuffer[x] == z) {
  388.         /* This case is hard to solve, and it may create high         */
  389.         /* intensity lines on polygon boundaries. To prevent from    */
  390.         /* that, update iff new color intensity is less than old on. */
  391.         if (ImageScanLine[x] < Color) ImageScanLine[x] = Color;
  392.         if (MaskScanLine != NULL) MaskScanLine[x] = 1;
  393.         }
  394.  
  395.         Az += Dz;
  396.         x++;
  397.         while (Az > 0) {
  398.         z++;
  399.         Az -= Dx;
  400.         }
  401.         if (GlblShadeInfo.Gouraud) {
  402.         if (Dc > 0) {
  403.             Ac += Dc;
  404.             while (Ac > 0) {
  405.             Color++;
  406.             Ac -= Dx;
  407.             }
  408.         }
  409.         else { /* Dc < 0 */
  410.             Ac -= Dc;
  411.             while (Ac > 0) {
  412.             Color--;
  413.             Ac -= Dx;
  414.             }
  415.         }
  416.         }
  417.     }
  418.     }
  419.     else { /* Dz < 0 */
  420.     while (x <= x2) {
  421.         /* Update buffers iff is closer to view point: */
  422.         if (ZBuffer[x] < z) {
  423.         ZBuffer[x] = z;
  424.         ImageScanLine[x] = Color;
  425.         if (MaskScanLine != NULL) MaskScanLine[x] = 1;
  426.         }
  427.         else if (ZBuffer[x] == z) {
  428.         /* This case is hard to solve, and it may create high         */
  429.         /* intensity lines on polygon boundaries. To prevent from    */
  430.         /* that, update iff new color intensity is less than old on. */
  431.         if (ImageScanLine[x] < Color) ImageScanLine[x] = Color;
  432.         if (MaskScanLine != NULL) MaskScanLine[x] = 1;
  433.         }
  434.  
  435.         Az -= Dz;
  436.         x++;
  437.         while (Az > 0) {
  438.         z--;
  439.         Az -= Dx;
  440.         }
  441.         if (GlblShadeInfo.Gouraud) {
  442.         if (Dc > 0) {
  443.             Ac += Dc;
  444.             while (Ac > 0) {
  445.             Color++;
  446.             Ac -= Dx;
  447.             }
  448.         }
  449.         else { /* Dc < 0 */
  450.             Ac -= Dc;
  451.             while (Ac > 0) {
  452.             Color--;
  453.             Ac -= Dx;
  454.             }
  455.         }
  456.         }
  457.     }
  458.     }
  459. }
  460.  
  461. #ifdef DEBUG
  462.  
  463. /*****************************************************************************
  464. * Routine to print the content of a given edge:                     *
  465. *****************************************************************************/
  466. void PrintHashTable(void)
  467. {
  468.     int i;
  469.     IPPolygonStruct *PPolygon;
  470.  
  471.     for (i = 0; i < GlblShadeInfo.ScrnYSize; i++)
  472.     if (PolyHashTable[i] != NULL) {
  473.         fprintf(stderr,
  474.             "\n***************** HashTable entry %d *****************\n", i);
  475.         PPolygon = PolyHashTable[i];
  476.         while (PPolygon) {
  477.             fprintf(stderr, "\t+++++++ Polygon:\n");
  478.             PrintPolygon(PPolygon);
  479.             PPolygon = PPolygon -> Pnext;
  480.         }
  481.         }
  482. }
  483.  
  484. /*****************************************************************************
  485. * Routine to print the content of a given edge:                     *
  486. *****************************************************************************/
  487. void PrintPolygon(IPPolygonStruct *PPolygon)
  488. {
  489.     int i;
  490.     IPVertexStruct *VList = PPolygon -> PVertex;
  491.  
  492.     for ( ; VList != NULL; VList = VList -> Pnext) {
  493.     fprintf(stderr, "\t%12f %12f %12f (Color = %d).\n",
  494.         PList -> Coord[0],
  495.         PList -> Coord[1],
  496.         PList -> Coord[2],
  497.         PList -> Color);
  498.     }
  499. }
  500.  
  501. /*****************************************************************************
  502. * Routine to print content of Image Scan Line buffer:                 *
  503. *****************************************************************************/
  504. void PrintImageScanLine(void)
  505. {
  506.     int i;
  507.  
  508.     for (i = 0; i < GlblShadeInfo.ScrnXSize; i++) {
  509.     if (i % 26 == 0) fprintf(stderr, "\n");
  510.     fprintf(stderr, "%02x ", ImageScanLine[i]);
  511.     }
  512. }
  513.  
  514. #endif /* DEBUG */
  515.